using System;
using System.Collections.Generic;

namespace Test.ConsoleProgram.Algorithm.Solution
{
    [TestDescription("算法: 0679. 24 点游戏")]
    public class No0679_JudgePoint24 : AbsBaseTestItem
    {
        /*
        你有 4 张写有 1 到 9 数字的牌。你需要判断是否能通过 *，/，+，-，(，) 的运算得到 24。
        注意:
            除法运算符 / 表示实数除法，而不是整数除法。例如 4 / (1 - 2/3) = 12 。
            每个运算符对两个数进行运算。特别是我们不能用 - 作为一元运算符。例如，[1, 1, 1, 1] 作为输入时，表达式 -1 - 1 - 1 - 1 是不允许的。
            你不能将数字连接在一起。例如，输入为 [1, 2, 1, 2] 时，不能写成 12 + 12 。
        */

        public override void OnTest()
        {
            Assert.TestExe(JudgePoint24, new int[] { 4, 1, 8, 7 }, true); // (8-4) * (7-1) = 24
            Assert.TestExe(JudgePoint24, new int[] { 1, 2, 1, 2 }, false);
        }

        public bool JudgePoint24(int[] nums)
        {
            const int TARGET = 24;
            const double EPSILON = 1e-6;
            const int ADD = 0, MULTIPLY = 1, SUBTRACT = 2, DIVIDE = 3;

            List<double> list = new List<double>();
            foreach (int num in nums)
            {
                list.Add(num);
            }
            bool solve(List<double> list)
            {
                if (list.Count == 0)
                {
                    return false;
                }
                if (list.Count == 1)
                {
                    return Math.Abs(list[0] - TARGET) < EPSILON;
                }
                int size = list.Count;
                for (int i = 0; i < size; i++)
                {
                    for (int j = 0; j < size; j++)
                    {
                        if (i != j)
                        {
                            List<double> list2 = new List<double>();
                            for (int k = 0; k < size; k++)
                            {
                                if (k != i && k != j)
                                {
                                    list2.Add(list[k]);
                                }
                            }
                            for (int k = 0; k < 4; k++)
                            {
                                if (k < 2 && i > j)
                                {
                                    continue;
                                }
                                if (k == ADD)
                                {
                                    list2.Add(list[i] + list[j]);
                                }
                                else if (k == MULTIPLY)
                                {
                                    list2.Add(list[i] * list[j]);
                                }
                                else if (k == SUBTRACT)
                                {
                                    list2.Add(list[i] - list[j]);
                                }
                                else if (k == DIVIDE)
                                {
                                    if (Math.Abs(list[j]) < EPSILON)
                                    {
                                        continue;
                                    }
                                    else
                                    {
                                        list2.Add(list[i] / list[j]);
                                    }
                                }
                                if (solve(list2))
                                {
                                    return true;
                                }
                                list2.RemoveAt(list2.Count - 1);
                            }
                        }
                    }
                }
                return false;
            }
            return solve(list);
        }
    }
}
